package backTrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 401. 二进制手表
 */
public class P401 {
    public List<String> readBinaryWatch(int turnedOn) {
        int minH = turnedOn - 6;
        minH = minH > 0 ? minH : 0;
        List<String> resultList = new ArrayList<>();
        for (int h = minH; h <= 4 && h <= turnedOn; h++) {
            int m = turnedOn - h;
            List<Integer> hoursList = new ArrayList<>();
            List<String> totalHours = new ArrayList<>();
            backTrackHours(new int[]{8, 4, 2, 1}, 0, h, hoursList, totalHours);
            List<Integer> minusList = new ArrayList<>();
            List<String> totalMinus = new ArrayList<>();
            backTrackMinus(new int[]{32, 16, 8, 4, 2, 1}, 0, m, minusList, totalMinus);
            for (String hour : totalHours) {
                for (String minu : totalMinus) {
                    resultList.add(hour + ":" + minu);
                }
            }
        }
        /*resultList.sort((a, b) -> {
            return a.compareTo(b);
        });*/
        return resultList;
    }

    void backTrackHours(int[] nums, int begin, int size, List<Integer> hoursList, List<String> totalList) {
        if (size == 0) {// 将时间放入
            int total = hoursList.stream().mapToInt(item -> item).sum();
            if (total >= 0 && total <= 11) {
                totalList.add(total + "");
            }
        } else {
            for (int i = begin; i < nums.length; i++) {
                hoursList.add(nums[i]);
                backTrackHours(nums, i + 1, size - 1, hoursList, totalList);
                hoursList.remove(hoursList.size() - 1);
            }
        }
    }

    void backTrackMinus(int[] nums, int begin, int size, List<Integer> hoursList, List<String> totalList) {
        if (size == 0) {// 将时间放入
            int total = hoursList.stream().mapToInt(item -> item).sum();
            if (total >= 0 && total <= 59) {
                totalList.add(total < 10 ? "0" + total : "" + total);
            }
        } else {
            for (int i = begin; i < nums.length; i++) {
                hoursList.add(nums[i]);
                backTrackMinus(nums, i + 1, size - 1, hoursList, totalList);
                hoursList.remove(hoursList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        List<String> times = new P401().readBinaryWatch(1);
        System.out.println(times);
    }
}
